package org.example.myleet.p691;

import java.util.*;

public class Solution {

    private int answer;

    public int minStickers(String[] stickers, String target) {
        answer = target.length() + 1;
        HashSet<Character> availableCharacters = new HashSet<>(26);
        List<int[]> stickerCharCounts = new ArrayList<>(stickers.length);
        for (String sticker : stickers) {
            int[] stickerCharCount = new int[26];
            for (char c : sticker.toCharArray()) {
                ++stickerCharCount[c - 'a'];
                availableCharacters.add(c);
            }
            stickerCharCounts.add(stickerCharCount);
        }
        int[] targetCharCount = new int[26];
        for (char c : target.toCharArray()) {
            if (!availableCharacters.contains(c)) {
                return -1;
            }
            ++targetCharCount[c - 'a'];
        }
        backtrack(targetCharCount, stickerCharCounts, 0, target.length());
        return answer > target.length() ? -1 : answer;
    }

    private void backtrack(int[] targetCharCount, List<int[]> stickerCharCounts, int num, int stop) {
        int i0 = isEnd(targetCharCount);
        if (i0 == -1) {
            if (answer > num) {
                answer = num;
            }
            return;
        }
        if (num > answer) {
            return;
        }
        if (num > stop) {
            return;
        }
        for (int[] stickerCharCount : stickerCharCounts) {
            if (stickerCharCount[i0] == 0) {
                continue;
            }
            int[] cacheCharCount = new int[26];
            for (int i = 0; i < 26; ++i) {
                int charCount = targetCharCount[i];
                if (charCount > 0) {
                    if (charCount <= stickerCharCount[i]) {
                        cacheCharCount[i] = charCount;
                        targetCharCount[i] = 0;
                    } else {
                        cacheCharCount[i] = stickerCharCount[i];
                        targetCharCount[i] = charCount - stickerCharCount[i];
                    }
                }
            }
            backtrack(targetCharCount, stickerCharCounts, num + 1, stop);
            //back track
            for (int i = 0; i < 26; ++i) {
                targetCharCount[i] += cacheCharCount[i];
            }
        }
    }

    private int isEnd(int[] targetCharCount) {
        for (int i = 0; i < 26; ++i) {
            if (targetCharCount[i] > 0) {
                return i;
            }
        }
        return -1;
    }
}
